#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define HASH_TABLE_SIZE 10007
#define IMAGE_WIDTH 10  // 先使用小尺寸测试
#define IMAGE_HEIGHT 10
#define TOTAL_PIXELS (IMAGE_WIDTH * IMAGE_HEIGHT)

typedef struct HashNode {
    int r, g, b;
    int count;
    struct HashNode *next;
} HashNode;

// 修复哈希函数，确保索引在范围内
unsigned int hash_function(int r, int g, int b) {
    unsigned int hash = (r * 73856093 ^ g * 19349663 ^ b * 83492791);
    return hash % HASH_TABLE_SIZE;
}

// 生成测试图像数据（简化版）
int** generate_test_image() {
    printf("Generating test image (%dx%d, total %d pixels)...\n", IMAGE_WIDTH, IMAGE_HEIGHT, TOTAL_PIXELS);
    
    int **pixels = (int**)malloc(TOTAL_PIXELS * sizeof(int*));
    if (!pixels) {
        printf("Error: Failed to allocate pixels array\n");
        return NULL;
    }
    
    // 初始化所有指针为NULL
    for (int i = 0; i < TOTAL_PIXELS; i++) {
        pixels[i] = NULL;
    }
    
    srand(time(NULL));
    
    // 使用简单的测试数据
    printf("Creating test colors...\n");
    for (int i = 0; i < TOTAL_PIXELS; i++) {
        pixels[i] = (int*)malloc(3 * sizeof(int));
        if (!pixels[i]) {
            printf("Error: Failed to allocate pixel %d\n", i);
            // 清理已分配的内存
            for (int j = 0; j < i; j++) {
                free(pixels[j]);
            }
            free(pixels);
            return NULL;
        }
        
        // 简单的测试颜色模式
        if (i % 4 == 0) {
            pixels[i][0] = 255; pixels[i][1] = 0; pixels[i][2] = 0;   // Red
        } else if (i % 4 == 1) {
            pixels[i][0] = 0; pixels[i][1] = 255; pixels[i][2] = 0;   // Green
        } else if (i % 4 == 2) {
            pixels[i][0] = 0; pixels[i][1] = 0; pixels[i][2] = 255;   // Blue
        } else {
            pixels[i][0] = 255; pixels[i][1] = 255; pixels[i][2] = 0; // Yellow
        }
    }
    
    printf("Test image generated successfully!\n");
    return pixels;
}

// 哈希表颜色直方图（修复版）
void histogram_hash(int **pixels, int pixel_count) {
    printf("\nCalculating color histogram using hash table...\n");
    
    // 检查输入有效性
    if (!pixels || pixel_count <= 0) {
        printf("Error: Invalid input parameters\n");
        return;
    }
    
    HashNode **hash_table = (HashNode**)calloc(HASH_TABLE_SIZE, sizeof(HashNode*));
    if (!hash_table) {
        printf("Error: Failed to allocate hash table\n");
        return;
    }
    
    clock_t start_time = clock();
    
    // 统计颜色（添加边界检查）
    for (int i = 0; i < pixel_count; i++) {
        // 检查像素数据是否有效
        if (!pixels[i]) {
            printf("Warning: Pixel %d is NULL, skipping\n", i);
            continue;
        }
        
        int r = pixels[i][0];
        int g = pixels[i][1];
        int b = pixels[i][2];
        
        // 验证颜色值范围
        if (r < 0 || r > 255 || g < 0 || g > 255 || b < 0 || b > 255) {
            printf("Warning: Invalid color value at pixel %d: (%d, %d, %d)\n", i, r, g, b);
            continue;
        }
        
        unsigned int index = hash_function(r, g, b);
        
        // 验证哈希索引
        if (index >= HASH_TABLE_SIZE) {
            printf("Error: Hash index out of bounds: %u\n", index);
            continue;
        }
        
        HashNode *current = hash_table[index];
        HashNode *prev = NULL;
        int found = 0;
        
        // 在链表中查找颜色
        while (current != NULL) {
            if (current->r == r && current->g == g && current->b == b) {
                current->count++;
                found = 1;
                break;
            }
            prev = current;
            current = current->next;
        }
        
        // 如果没找到，创建新节点
        if (!found) {
            HashNode *new_node = (HashNode*)malloc(sizeof(HashNode));
            if (!new_node) {
                printf("Error: Failed to allocate new hash node\n");
                continue;
            }
            new_node->r = r;
            new_node->g = g;
            new_node->b = b;
            new_node->count = 1;
            new_node->next = NULL;
            
            if (prev == NULL) {
                hash_table[index] = new_node;
            } else {
                prev->next = new_node;
            }
        }
    }
    
    clock_t end_time = clock();
    double time_used = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
    
    // 统计结果
    int total_colors = 0;
    int max_count = 0;
    HashNode *max_color_node = NULL;
    
    printf("Analysis completed, processing results...\n");
    
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        HashNode *current = hash_table[i];
        while (current != NULL) {
            total_colors++;
            if (current->count > max_count) {
                max_count = current->count;
                max_color_node = current;
            }
            current = current->next;
        }
    }
    
    // 输出摘要
    printf("\n=== Color Histogram Results ===\n");
    printf("Total pixels: %d\n", pixel_count);
    printf("Unique colors: %d\n", total_colors);
    printf("Processing time: %.4f seconds\n", time_used);
    
    if (max_color_node != NULL) {
        printf("Most frequent color: RGB(%d, %d, %d), Count: %d\n", 
               max_color_node->r, max_color_node->g, max_color_node->b, max_count);
    }
    
    // 输出前几个颜色
    printf("\nColor distribution:\n");
    int colors_to_show = (total_colors < 10) ? total_colors : 10;
    printf("Showing %d colors:\n", colors_to_show);
    
    int shown = 0;
    for (int i = 0; i < HASH_TABLE_SIZE && shown < colors_to_show; i++) {
        HashNode *current = hash_table[i];
        while (current != NULL && shown < colors_to_show) {
            double percentage = (double)current->count / pixel_count * 100;
            printf("RGB(%3d,%3d,%3d): %d (%.1f%%)\n", 
                   current->r, current->g, current->b, current->count, percentage);
            shown++;
            current = current->next;
        }
    }
    
    // 释放内存
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        HashNode *current = hash_table[i];
        while (current != NULL) {
            HashNode *temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(hash_table);
}

// 释放图像内存
void free_image(int **pixels, int count) {
    if (!pixels) return;
    
    for (int i = 0; i < count; i++) {
        if (pixels[i]) {
            free(pixels[i]);
        }
    }
    free(pixels);
}

int main() {
    printf("=== Image Color Histogram Test ===\n");
    
    // 生成测试图像
    int **test_image = generate_test_image();
    if (!test_image) {
        printf("Failed to generate test image!\n");
        return 1;
    }
    
    // 计算直方图
    histogram_hash(test_image, TOTAL_PIXELS);
    
    // 释放内存
    free_image(test_image, TOTAL_PIXELS);
    
    printf("\nTest completed successfully!\n");
    return 0;
}